#ifndef __HASH_TABLE_H__
#define __HASH_TABLE_H__
#include <cstddef>
#include <cstring>
#include <cstdlib>
#include <iostream>

using namespace std;

#define TABLE_SIZE 1024

template <class Type>
struct NODE {
    char key[100];
    Type val;
    struct NODE *next;
};

template <class Type>
class HashTable {
public:
    HashTable();
    ~HashTable();

    bool insert(const char *key, Type val);
    bool remove(const char *key);

    bool getVal(const char *key, Type &val);

    bool clear();
    size_t size();
    float occupancy();

private:
    int calcHashVal(const char *key);
    bool removeEntry(NODE<Type> *node);

private:
    NODE<Type> *table[TABLE_SIZE];
    int entry_num;
    int node_num;
};

template<class Type>
HashTable<Type>::HashTable() {
    memset(table, 0, sizeof(NODE<Type> *) * TABLE_SIZE);
    entry_num = 0;
    node_num = 0;
}

template<class Type>
bool HashTable<Type>::removeEntry(NODE<Type> *node) {
    if (node == NULL) {
        return true;
    }

    NODE<Type> *tmp_node;
    while (node) {
        tmp_node = node->next;
        free(node);
        --node_num;
        node = tmp_node;
    }
    --entry_num;

    return true;
}

template<class Type>
int HashTable<Type>::calcHashVal(const char *key) {
    size_t key_size = strlen(key);
    size_t i;
    int sum = 0;
    for (i = 0; i < key_size; i++) {
        sum += (int)key[i];
    }

    sum = sum & (TABLE_SIZE - 1);

    return sum;
}

template<class Type>
HashTable<Type>::~HashTable() {
    int i;
    for (i = 0; i < TABLE_SIZE; i++) {
        removeEntry(table[i]);
        table[i] = NULL;
    }
}

template<class Type>
bool HashTable<Type>::insert(const char *key, Type val) {
    int index = calcHashVal(key);
    NODE<Type> *node = table[index];
    if (node == NULL) {
        NODE<Type> *tmp_node = (NODE<Type> *)malloc(sizeof(NODE<Type>)); 
        ++node_num;
        ++entry_num;
        if (tmp_node == NULL) {
            cout << "Allocate node error, NULL!" << endl;
            return false;
        }
        tmp_node->next = NULL;
        strcpy(tmp_node->key, key);
        tmp_node->val = val;
        table[index] = tmp_node;
    }
    else {
        // go through each node to check whether the key already exists
        NODE<Type> *tmp_node;
        do {
            int ret_code = strcmp(key, node->key);
            if (ret_code == 0) {
                break;
            }
            tmp_node = node;
            node = node->next;
        }
        while(node);

        if (node) {
            node->val = val;
        }
        else {
            tmp_node->next = (NODE<Type> *) malloc(sizeof(NODE<Type>));
            ++entry_num;
            memset(tmp_node->next, 0, sizeof(NODE<Type>));
            strcpy(tmp_node->key, key);
            tmp_node->val = val;
        }
    }

    return true;
}

template<class Type>
bool HashTable<Type>::remove(const char *key) {
    int index = calcHashVal(key);
    NODE<Type> *node = table[index];
    NODE<Type> *node_pre;

    if (strcmp(node->key, key) == 0) {
        table[index] = node->next;
        free(node);

        return true;
    }
    else {
        node_pre = node;
        node = node->next;
        while (node) {
            if (strcmp(node->key, key) == 0) {
                break;
            }
            node_pre = node;
            node = node->next;
        }

        if (node) {
            node_pre->next = node->next;
            free(node);
            return true;
        }
        else {
            return false;
        }
    }
}

template<class Type>
bool HashTable<Type>::getVal(const char *key, Type &val) {
    int index = calcHashVal(key);
    NODE<Type> *node = table[index];
    while (node) {
        if (strcmp(node->key, key) == 0) {
            break;
        }
        node = node->next;
    }

    if (node) {
        val = node->val;
        return true;
    }

    return false;
}

template<class Type>
size_t HashTable<Type>::size() {
    return node_num;
}

template<class Type>
bool HashTable<Type>::clear() {
    int i;
    for (i = 0; i < TABLE_SIZE; i++) {
        removeEntry(table[i]);
        table[i] = NULL;
    }

    node_num = 0;
    entry_num = 0;

    return true;
}

template<class Type>
float HashTable<Type>::occupancy() {
    return (float)entry_num/node_num;
}

#endif

